Search Results

Documents authored by Ambainis, Andris

Document
DOI: 10.4230/LIPIcs.TQC.2023.7
Improved Algorithm and Lower Bound for Variable Time Quantum Search

Authors: Andris Ambainis, Martins Kokainis, and Jevgēnijs Vihrovs

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract
We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable time search with complexity O(√Tlog n) where T = ∑_{i = 1}ⁿ t_i² with t_i denoting the time to check the i^th item. Our second result is a quantum lower bound of Ω(√{Tlog T}). Both the algorithm and the lower bound improve over previously known results by a factor of √{log T} but the algorithm is also substantially simpler than the previously known quantum algorithms.
Cite as

Andris Ambainis, Martins Kokainis, and Jevgēnijs Vihrovs. Improved Algorithm and Lower Bound for Variable Time Quantum Search. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.TQC.2023.7,
  author =	{Ambainis, Andris and Kokainis, Martins and Vihrovs, Jevg\={e}nijs},
  title =	{{Improved Algorithm and Lower Bound for Variable Time Quantum Search}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.7},
  URN =		{urn:nbn:de:0030-drops-183177},
  doi =		{10.4230/LIPIcs.TQC.2023.7},
  annote =	{Keywords: quantum search, amplitude amplification}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.24
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

Authors: Andris Ambainis and Aleksandrs Belovs

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
While it is known that there is at most a polynomial separation between quantum query complexity and the polynomial degree for total functions, the precise relationship between the two is not clear for partial functions. In this paper, we demonstrate an exponential separation between exact polynomial degree and approximate quantum query complexity for a partial Boolean function. For an unbounded alphabet size, we have a constant versus polynomial separation.
Cite as

Andris Ambainis and Aleksandrs Belovs. An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.CCC.2023.24,
  author =	{Ambainis, Andris and Belovs, Aleksandrs},
  title =	{{An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{24:1--24:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.24},
  URN =		{urn:nbn:de:0030-drops-182943},
  doi =		{10.4230/LIPIcs.CCC.2023.24},
  annote =	{Keywords: Polynomials, Quantum Adversary Bound, Separations in Query Complexity}
}
Document
DOI: 10.4230/LIPIcs.TQC.2021.6
A Note About Claw Function with a Small Range

Authors: Andris Ambainis, Kaspars Balodis, and Jānis Iraids

Published in: LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)

Abstract
In the claw detection problem we are given two functions f:D → R and g:D → R (|D| = n, |R| = k), and we have to determine if there is exist x,y ∈ D such that f(x) = g(y). We show that the quantum query complexity of this problem is between Ω(n^{1/2}k^{1/6}) and O(n^{1/2+ε}k^{1/4}) when 2 ≤ k < n.
Cite as

Andris Ambainis, Kaspars Balodis, and Jānis Iraids. A Note About Claw Function with a Small Range. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 6:1-6:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.TQC.2021.6,
  author =	{Ambainis, Andris and Balodis, Kaspars and Iraids, J\={a}nis},
  title =	{{A Note About Claw Function with a Small Range}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{6:1--6:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-198-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{197},
  editor =	{Hsieh, Min-Hsiu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.6},
  URN =		{urn:nbn:de:0030-drops-140013},
  doi =		{10.4230/LIPIcs.TQC.2021.6},
  annote =	{Keywords: collision, claw, quantum query complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.8
Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language

Authors: Andris Ambainis, Kaspars Balodis, Jānis Iraids, Kamil Khadiev, Vladislavs Kļevickis, Krišjānis Prūsis, Yixin Shen, Juris Smotrovs, and Jevgēnijs Vihrovs

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most k. We call this the Dyck_{k,n} problem. We prove a lower bound of Ω(c^k √n), showing that the complexity of this problem increases exponentially in k. Here n is the length of the word. When k is a constant, this is interesting as a representative example of star-free languages for which a surprising Õ(√n) query quantum algorithm was recently constructed by Aaronson et al. [Scott Aaronson et al., 2018]. Their proof does not give rise to a general algorithm. When k is not a constant, Dyck_{k,n} is not context-free. We give an algorithm with O(√n(log n)^{0.5k}) quantum queries for Dyck_{k,n} for all k. This is better than the trival upper bound n for k = o({log(n)}/{log log n}). Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the "balanced parentheses" problem into the grid, we show a lower bound of Ω(n^{1.5-ε}) for the directed 2D grid and Ω(n^{2-ε}) for the undirected 2D grid. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions.
Cite as

Andris Ambainis, Kaspars Balodis, Jānis Iraids, Kamil Khadiev, Vladislavs Kļevickis, Krišjānis Prūsis, Yixin Shen, Juris Smotrovs, and Jevgēnijs Vihrovs. Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.MFCS.2020.8,
  author =	{Ambainis, Andris and Balodis, Kaspars and Iraids, J\={a}nis and Khadiev, Kamil and K\c{l}evickis, Vladislavs and Pr\={u}sis, Kri\v{s}j\={a}nis and Shen, Yixin and Smotrovs, Juris and Vihrovs, Jevg\={e}nijs},
  title =	{{Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.8},
  URN =		{urn:nbn:de:0030-drops-126774},
  doi =		{10.4230/LIPIcs.MFCS.2020.8},
  annote =	{Keywords: Quantum query complexity, Quantum algorithms, Dyck language, Grid path}
}
Document
DOI: 10.4230/LIPIcs.TQC.2020.9
Quantum Algorithms for Computational Geometry Problems

Authors: Andris Ambainis and Nikita Larka

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract
We study quantum algorithms for problems in computational geometry, such as Point-On-3-Lines problem. In this problem, we are given a set of lines and we are asked to find a point that lies on at least 3 of these lines. Point-On-3-Lines and many other computational geometry problems are known to be 3Sum-Hard. That is, solving them classically requires time Ω(n^{2-o(1)}), unless there is faster algorithm for the well known 3Sum problem (in which we are given a set S of n integers and have to determine if there are a, b, c ∈ S such that a + b + c = 0). Quantumly, 3Sum can be solved in time O(n log n) using Grover’s quantum search algorithm. This leads to a question: can we solve Point-On-3-Lines and other 3Sum-Hard problems in O(n^c) time quantumly, for c<2? We answer this question affirmatively, by constructing a quantum algorithm that solves Point-On-3-Lines in time O(n^{1 + o(1)}). The algorithm combines recursive use of amplitude amplification with geometrical ideas. We show that the same ideas give O(n^{1 + o(1)}) time algorithm for many 3Sum-Hard geometrical problems.
Cite as

Andris Ambainis and Nikita Larka. Quantum Algorithms for Computational Geometry Problems. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 9:1-9:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.TQC.2020.9,
  author =	{Ambainis, Andris and Larka, Nikita},
  title =	{{Quantum Algorithms for Computational Geometry Problems}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{9:1--9:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.9},
  URN =		{urn:nbn:de:0030-drops-120687},
  doi =		{10.4230/LIPIcs.TQC.2020.9},
  annote =	{Keywords: Quantum algorithms, quantum search, computational geometry, 3Sum problem, amplitude amplification}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.8
All Classical Adversary Methods are Equivalent for Total Functions

Authors: Andris Ambainis, Martins Kokainis, Krisjanis Prusis, and Jevgenijs Vihrovs

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity fbs(f). That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. For partial functions, we show unbounded separations between fbs(f) and other adversary bounds, as well as between the relational and Kolmogorov complexity bounds. We also show that, for partial functions, fractional block sensitivity cannot give lower bounds larger than sqrt(n * bs(f)), where n is the number of variables and bs(f) is the block sensitivity. Then we exhibit a partial function f that matches this upper bound, fbs(f) = Omega(sqrt(n * bs(f))).
Cite as

Andris Ambainis, Martins Kokainis, Krisjanis Prusis, and Jevgenijs Vihrovs. All Classical Adversary Methods are Equivalent for Total Functions. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.STACS.2018.8,
  author =	{Ambainis, Andris and Kokainis, Martins and Prusis, Krisjanis and Vihrovs, Jevgenijs},
  title =	{{All Classical Adversary Methods are Equivalent for Total Functions}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.8},
  URN =		{urn:nbn:de:0030-drops-84953},
  doi =		{10.4230/LIPIcs.STACS.2018.8},
  annote =	{Keywords: Randomized Query Complexity, Lower Bounds, Adversary Bounds, Fractional Block Sensitivity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.4
Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions

Authors: Andris Ambainis, Martins Kokainis, and Robin Kothari

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Göös, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) query complexity and subcube partition complexity, which is also essentially optimal. We also establish a nearly power 1.5 separation between quantum query complexity and subcube partition complexity, the first superlinear separation between the two measures. Lastly, we show a quadratic separation between quantum query complexity and one-sided subcube partition complexity. Our query complexity separations use the recent cheat sheet framework of Aaronson, Ben-David, and Kothari. Our query functions are built up in stages by alternating function composition with the cheat sheet construction. The communication complexity separation follows from "lifting" the query separation to communication complexity.
Cite as

Andris Ambainis, Martins Kokainis, and Robin Kothari. Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.CCC.2016.4,
  author =	{Ambainis, Andris and Kokainis, Martins and Kothari, Robin},
  title =	{{Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.4},
  URN =		{urn:nbn:de:0030-drops-58471},
  doi =		{10.4230/LIPIcs.CCC.2016.4},
  annote =	{Keywords: Query Complexity, Communication Complexity, Subcube Partition Complexity, Partition Bound}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.25
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality

Authors: Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, and Juris Smotrovs

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by epsilon<1/2 iff f can be approximated by a degree-2 polynomial with error bounded by epsilon'<1/2. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [Aaronson/Ambainis, STOC 2015]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms. We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ~Omega(n) quantum queries but can be represented by a block-multilinear polynomial of degree ~O(sqrt(n)). Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms. Second, for any constant degree k, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from [Aaronson/Ambainis, STOC 2015], showing that one can estimate the value of any bounded degree-k polynomial p:{0,1}^n -> [-1,1] with O(n^{1-1/(2k)) queries.
Cite as

Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, and Juris Smotrovs. Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{aaronson_et_al:LIPIcs.CCC.2016.25,
  author =	{Aaronson, Scott and Ambainis, Andris and Iraids, Janis and Kokainis, Martins and Smotrovs, Juris},
  title =	{{Polynomials, Quantum Query Complexity, and Grothendieck's Inequality}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.25},
  URN =		{urn:nbn:de:0030-drops-58394},
  doi =		{10.4230/LIPIcs.CCC.2016.25},
  annote =	{Keywords: quantum algorithms, Boolean functions, approximation by polynomials, Grothendieck's inequality}
}
Document
DOI: 10.4230/LIPIcs.TQC.2013.146
Provable Advantage for Quantum Strategies in Random Symmetric XOR Games

Authors: Andris Ambainis and Janis Iraids

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)

Abstract
Non-local games are widely studied as a model to investigate the properties of quantum mechanics as opposed to classical mechanics. In this paper, we consider a subset of non-local games: symmetric XOR games of n players with 0-1 valued questions. For this class of games, each player receives an input bit and responds with an output bit without communicating to the other players. The winning condition only depends on XOR of output bits and is constant w.r.t. permutation of players. We prove that for almost any n-player symmetric XOR game the entangled value of the game is Theta((sqrt(ln(n)))/(n^{1/4})) adapting an old result by Salem and Zygmund on the asymptotics of random trigonometric polynomials. Consequently, we show that the classical-quantum gap is Theta(sqrt(ln(n))) for almost any symmetric XOR game.
Cite as

Andris Ambainis and Janis Iraids. Provable Advantage for Quantum Strategies in Random Symmetric XOR Games. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 146-156, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.TQC.2013.146,
  author =	{Ambainis, Andris and Iraids, Janis},
  title =	{{Provable Advantage for Quantum Strategies in Random Symmetric XOR Games}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{146--156},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.146},
  URN =		{urn:nbn:de:0030-drops-43156},
  doi =		{10.4230/LIPIcs.TQC.2013.146},
  annote =	{Keywords: Random Symmetric XOR games, Entanglement}
}
Document
DOI: 10.4230/LIPIcs.TQC.2013.263
Exact Quantum Query Complexity of EXACT and THRESHOLD

Authors: Andris Ambainis, Janis Iraids, and Juris Smotrovs

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)

Abstract
A quantum algorithm is exact if it always produces the correct answer, on any input. Coming up with exact quantum algorithms that substantially outperform the best classical algorithm has been a quite challenging task. In this paper, we present two new exact quantum algorithms for natural problems: - for the problem EXACT_k^n in which we have to determine whether the sequence of input bits x_1, ..., x_n contains exactly k values x_i=1; - for the problem THRESHOLD_k^n in which we have to determine if at least k of n input bits are equal to 1.
Cite as

Andris Ambainis, Janis Iraids, and Juris Smotrovs. Exact Quantum Query Complexity of EXACT and THRESHOLD. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 263-269, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.TQC.2013.263,
  author =	{Ambainis, Andris and Iraids, Janis and Smotrovs, Juris},
  title =	{{Exact Quantum Query Complexity of EXACT and THRESHOLD}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{263--269},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.263},
  URN =		{urn:nbn:de:0030-drops-43261},
  doi =		{10.4230/LIPIcs.TQC.2013.263},
  annote =	{Keywords: Quantum query algorithms, Complexity of Boolean functions}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.446
Optimal quantum query bounds for almost all Boolean functions

Authors: Andris Ambainis, Arturs Backurs, Juris Smotrovs, and Ronald de Wolf

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We show that almost all n-bit Boolean functions have bounded-error quantum query complexity at least n/2, up to lower-order terms. This improves over an earlier n/4 lower bound of Ambainis (A. Ambainis, 1999), and shows that van Dam's oracle interrogation (W. van Dam, 1998) is essentially optimal for almost all functions. Our proof uses the fact that the acceptance probability of a T-query algorithm can be written as the sum of squares of degree-T polynomials.
Cite as

Andris Ambainis, Arturs Backurs, Juris Smotrovs, and Ronald de Wolf. Optimal quantum query bounds for almost all Boolean functions. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 446-453, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.STACS.2013.446,
  author =	{Ambainis, Andris and Backurs, Arturs and Smotrovs, Juris and de Wolf, Ronald},
  title =	{{Optimal quantum query bounds for almost all Boolean functions}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{446--453},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.446},
  URN =		{urn:nbn:de:0030-drops-39557},
  doi =		{10.4230/LIPIcs.STACS.2013.446},
  annote =	{Keywords: Quantum computing, query complexity, lower bounds, polynomial method}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.636
Variable time amplitude amplification and quantum algorithms for linear algebra problems

Authors: Andris Ambainis

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
Quantum amplitude amplification is a method of increasing a success probability of an algorithm from a small epsilon>0 to Theta(1) with less repetitions than classically. In this paper, we generalize quantum amplitude amplification to the case when parts of the algorithm that is being amplified stop at different times. We then apply the new variable time amplitude amplification to give two new quantum algorithms for linear algebra problems. Our first algorithm is an improvement of Harrow et al. algorithm for solving systems of linear equations. We improve the running time of the algorithm from O(k^2 log N) to O(k log^3 k log N) where k is the condition number of the system of equations. Our second algorithm tests whether a matrix A is singular or far from singular, faster then the previously known algorithms.
Cite as

Andris Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 636-647, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{ambainis:LIPIcs.STACS.2012.636,
  author =	{Ambainis, Andris},
  title =	{{Variable time amplitude amplification and quantum algorithms for linear algebra problems}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{636--647},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.636},
  URN =		{urn:nbn:de:0030-drops-34261},
  doi =		{10.4230/LIPIcs.STACS.2012.636},
  annote =	{Keywords: quantum computing, quantum algorithms, amplitude amplification, linear equations}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1333
Quantum search with variable times

Authors: Andris Ambainis

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
Since Grover's seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of $n$ items $x_1, ldots, x_n$ and we would like to find $i: x_i=1$. We consider a new variant of this problem in which evaluating $x_i$ for different $i$ may take a different number of time steps. Let $t_i$ be the number of time steps required to evaluate $x_i$. If the numbers $t_i$ are known in advance, we give an algorithm that solves the problem in $O(sqrt{t_1^2+t_2^2+ldots+t_n^2)$ steps. This is optimal, as we also show a matching lower bound. The case, when $t_i$ are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.
Cite as

Andris Ambainis. Quantum search with variable times. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 49-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{ambainis:LIPIcs.STACS.2008.1333,
  author =	{Ambainis, Andris},
  title =	{{Quantum search with variable times}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{49--60},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1333},
  URN =		{urn:nbn:de:0030-drops-13333},
  doi =		{10.4230/LIPIcs.STACS.2008.1333},
  annote =	{Keywords: }
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact